CPU Scheduling Algorithm

tags: IT鐵人

作用

因為同時處理很多的process，所以誰先誰後，或是輪流執行的方式就成為必須的討論。

每個演算法都會有其優缺點，在考量不同的面相時會有不同的選擇，比如單位時間的產量、特定process即時完成、不可造成process永遠執行不到。

以下會一一討論各個Algorithm。

FIFO

FIFO全名稱為First In First Out，顧名思義就是先到先做，做完才輪到下一個process。

舉例來說：

假設大家都是在t=0進來，依照數字的順序執行，那麼P1會在t=24完成，P2在t=27完成，P3在t=30完成。

Average waiting time為(24+27)/3=17
Average turnaround time為(24+27+30)/3=27

前面可以看出來不論是等待時間，或是完成時間都較高，FIFO很單純，具有下列特性。

1.簡單，易實施
2.排班效能最差(Average waiting time及Average turnaround time最長)
3.可能會遭遇Convoy Effect(上面的P1導致)
4.公平(任何process都會輪到)
5.No Starvation(不會輪不到)
6.屬於Non-preemptive法則(無法插隊)

SJF

SJF的全名為Shortest-Job-First，顧名思義就是執行時間最短的先做。

舉例來說：

假設大家一樣是在t=0進來，那麼P4會在t=3完成，P1會在t=9完成，P3會在t=16完成，P2會在t=24完成。

Average waiting time為(3+9+16)/4=7

SJF單純討論誰最快就先跑誰，具有以下特性：

1.排班效益最佳(Average waiting time最小)
2.不公平，偏好short job
3.對long-burst-time job可能有starvation(一直無法執行)
4.屬於Non-preemptive法則
5.因為不好預測，所以不易實施

SRTF

SRTF全名為Shortest-Remaining Time First，跟SJF不同的地方在於他看的是剩下的時間，如果發現有process更快，系統會允許該process插隊。

舉例來說：

因為比較複雜，杰哥畫圖解釋

在process進來時考慮剩下的執行時間，執行流程會變成上面的樣子。

Average waiting time為(9+2+15)/4=13/2

計算時要考慮大家的到達時間，比前面的麻煩一點，SRTF有以下特性：

1.與SJF相比，有更好的排班效益，不過會付出更多的context switch代價
2.不公平
3.有starvation
4.preemptive法則

Priority Scheduling

Priority Scheduling會先給予每個process一個priority，根據priority決定誰可以先執行，遇到priority一樣的話，則使用FIFO執行。

舉例來說：

這個也複雜到需要畫圖解釋

Average waiting time為(19+10+1)/4=15/2

Priority Scheduling單純看Priority決定順序，定義的方式由OS或是使用者定義，特性如下：

1.可參數化的法則(用Arrival time定義=>FIFO，用CPU burst time定義=>SJF)
2.不公平
3.可以Preemptive or Non-Preemptive
4.會有Starvation
5.可與RR結合(同樣priority RR)

RR

RR的全名是Round-Robin，這個字也會用在循環賽，代表的意思就是大家輪流，也就是說每個process會輪流執行一段時間，如果提早結束或是時間到了，就會交給下一個process執行。

直接用下圖舉例說明：

Average waiting time為16/3

RR的輪流策略具有以下特性：

1.常用於Time-sharing system
2.公平(每一輪都FIFO order)
3.No Starvation
4.Preemptive(被迫放CPU)
5.RR效能取決於Quantum大小的制定(如果Quantum無限大=>FIFO，非常小=>context switch頻繁導致CPU utilization趨近於0)
經驗表示，如果Q的大小使80%的process在Q內完成，則效能很好。

小結

上面介紹了許多Scheduling Algorithm，這些都是應用在process上，下一篇會介紹thread，同時也稱為light weight process，那就下篇見ㄅ~

What Algorithm means